#include <string.h> //bzero()
#include <setjmp.h>
#include "../myTypes.h"
#include "../bit.h"
#include "../barre.h"
#include "prefix-tree.h"
#include "lz78.h"

#define DICOMAXSIZE	1000000	//nombre de noeud max pour l'apc


typedef struct{
	bloc_t	id;		//i
	byte	c;		//j
	int		facLen;	//longueur du facteur
} lz78code_t;


static ptree_t mem_tree[DICOMAXSIZE];		//mémoire réservée à l'apc
static int allocated;			//nombre de noeud utilisé dans mem_tree

static jmp_buf env;	//pour les branchements non locaux (exceptions)
static int exception;	//valeur de l'exception
static int verbose;     //le verbose mode


//-----------------------------------------------------------------------------
void LZ78_init()
//-----------------------------------------------------------------------------
//Phase d'initialisation de l'algorithme
{
	allocated=0;	//Le premier noeud représente le mot vide ε
	memset(mem_tree, 0, DICOMAXSIZE*sizeof(ptree_t));
}


//-----------------------------------------------------------------------------
void LZ78_addWordToDic(ptree_t * w, byte b)
//-----------------------------------------------------------------------------
//ajouter
{
	ptree_t * n= &mem_tree[allocated+1];

	allocated++;
	//Ajout du nouveau mot au dictionaire
	n->id= allocated;
	n->c = b;
	n->right = NULL;
	PTree_cat(w,n);
}



//-----------------------------------------------------------------------------
lz78code_t LZ78_getCode(bitbuf_t * buf)
//-----------------------------------------------------------------------------
// récupère le code en lisant dans l'ACP (arbre de commun sufixes)
// le curseur du buffer est mis à jour
{
	lz78code_t	code;
	ptree_t * node = &mem_tree[0]; //noeud courrant de l'APC initialisé à la racine
	ptree_t * n;	//pointeur de sauvegarde temporaire
	byte * pcurs = buf->curs;

	//code.facLen = 0;

	if(verbose)
	  printf("getcode() getpos(bus)=%d buf->len =%d\n",bit_getpos(buf), buf->len);

	while( ( bit_getpos(buf) < buf->len ) && (n=PTree_getNode(node,*buf->curs)) )
	{
		node=n;
		buf->curs++;
		//code.facLen++;
	}
	code.id 	= node->id;
	code.c		= *buf->curs;
	if( bit_getpos(buf) < buf->len ) //Si on est pas en fin de buffer
	{
		buf->curs++;
		code.facLen = buf->curs - pcurs;	//longueur du facteur
	}else{
		//Sinon lever une exception
		//printf("Exception node.id=%d \n", (int)node->id);
		exception = node->id;
		longjmp(env,1);
	}



	return code;
}


//-----------------------------------------------------------------------------
bitcount_t LZ78_writeCode(lz78code_t * code, bitbuf_t * dst)
//-----------------------------------------------------------------------------
//Écrire le code dans le buffer => retourne le nombre de bits ecrit
{
	bitcount_t wrote=8;
	bitcount_t idLen=0;
	unsigned int i;

	//calcul du nombre de bit nécessaire en fonction du nombre de noeud de l'APC
	for(i=allocated; i!=0; i>>=1){idLen++;}

	//  printf("log²(%d)=%d\n",allocated, idLen);
	bit_write(dst,code->id,idLen);
	//bit_printbloc((bloc_t)code->c);
	bit_write(dst,(bloc_t)code->c,8);

	wrote+=idLen;

	return wrote;
}


//-----------------------------------------------------------------------------
bitcount_t LZ78_readCode(lz78code_t * code, bitbuf_t * src)
//-----------------------------------------------------------------------------
//Lire un code depuis le buffer => retroune le nombre de bits lus
{
	bitcount_t read=8;
	bitcount_t idLen=0;
	unsigned int i;

	//calcul du nombre de bit nécessaire en fonction du nombre de noeud de l'APC
	for(i=allocated; i!=0; i>>=1){idLen++;}

	//printf("log²(%d)=%d\n",allocated, idLen);
	code->id = bit_read(src,idLen);
	code->c	= bit_read(src,8);
	code->facLen =0;	//non connu

	read+=idLen;

	return read;
}

//-----------------------------------------------------------------------------
void LZ78_encode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	size_t i;
	lz78code_t	code;
	unsigned int idLen=0, cpt=0,bc=0;

	if(setjmp(env)==0)
		//TRY{
	{
		for(i=0; i<src->len;)
		{
			if(allocated-1 >= DICOMAXSIZE){//On reconstruit un nouvel APC
				LZ78_init();
				//printf("\nReconstruction de l'arbre\n");
			}
			code=LZ78_getCode(src);
			bc=LZ78_writeCode(&code, dst);
			cpt+=bc;
			if(verbose)
			  printf("%d - (%d,%c) %d %d bits \n",cpt,code.id,code.c,code.facLen,bc);
			//LZ78_writeCode(&code, dst);
			LZ78_addWordToDic(&mem_tree[code.id], code.c);
			i+= (code.facLen * 8);
		}
		dst->len = bit_getpos(dst);
		//}CATCH(int exception){
	}else{
		// cas spécial de fin de buffer: on écrit que le début du code
		for(i=allocated; i!=0; i>>=1){idLen++;}
		bit_write(dst,exception,idLen);
		//printf("(%d,Ø) %d bits  ",(int)exception,idLen);
		dst->len = bit_getpos(dst);
		//printf("dst->len = %d",dst->len);
	}
	//}
}


//-----------------------------------------------------------------------------
int LZ78_writeHeader(FILE * out, lz78header * header)
//-----------------------------------------------------------------------------
{
	fwrite(header->id,4,1,out);
	fwrite(&header->oriSize,4,1,out);
	fwrite(&header->bufLen, 2, 1, out);

	return 10;
}

//-----------------------------------------------------------------------------
void LZ78_readHeader(FILE * in, lz78header * header)
//-----------------------------------------------------------------------------
{
	header->bufLen =0;
	header->oriSize=0;

	fread(header->id,4,1,in);
	fread(&header->oriSize,4,1,in);
	fread(&header->bufLen, 2, 1, in);
}


//-----------------------------------------------------------------------------
void LZ78_decode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	size_t i;
	int wordLen=0;
	bitcount_t read=0;
	lz78code_t	code;
	ptree_t * node;

	for(i=0; i<src->len; i+= read)
	{
		if(allocated-1 >= DICOMAXSIZE){//On reconstruit un nouvel APC
			LZ78_init();
			//printf("\nReconstruction de l'arbre\n");
		}

		//printf("i=%d - ",i);
		read = LZ78_readCode(&code, src);

		node = &mem_tree[code.id];
		wordLen = PTree_readWord(node,dst->curs);
		dst->curs+= wordLen;

		if(i+read <= src->len)
		{
			//printf("readCode %dbits (%d,%c)\n",read,code.id, code.c);

			//ajouter code.c
			LZ78_addWordToDic(node,code.c);

			//ecrit c
			*dst->curs = code.c;
			dst->curs++;

		}else{ //fin de buffer
			//rien à faire
			//printf("readCode %ddbits (%d,Ø)\n",read,code.id);
		}
	}

	//printf("i=%d",i);fflush(stdout);
	dst->len = bit_getpos(dst);
}

//-----------------------------------------------------------------------------
void LZ78_compress(FILE * out, FILE * in, int verb)
//-----------------------------------------------------------------------------
//premier rush on fixe les buffers a 8ko et on gaspille des bits dans le fichier
//TODO ne plus faire de gaspillage de bits
{
        verbose = verb;
	bitbuf_t src,dst;
	int bufLen = 8192;	//8ko
	int len=0;
	size_t read=0,wrote=0;
	size_t fileLen;
	lz78header header={LZ78ID,bufLen,0};

	//calcul de la taille du fichier
	fseek(in,0,SEEK_END);
	fileLen = ftell(in);
	rewind(in);


	//Écriture de l'en-tête
	if(verbose)
	  printf("filLen= %d\n",fileLen);
	header.oriSize = fileLen;
	wrote = LZ78_writeHeader(out,&header);

	//initialisation des buffers
	bit_initBuf(&src,bufLen*8);
	bit_initBuf(&dst,(bufLen+(bufLen/2))*8);	//prévoir +1/3 de mémoire en cas de dépression

	//initialisation de l'algo
	LZ78_init();
	updateBar(0.);

	while(!feof(in))
	{
		len=fread(src.data, 1, bufLen, in);
		read += len;
		//printf("\nlen=%d read=%d wrote=%d\n",len,wrote,read);
		updateBar((double)read/fileLen);
		if(verbose)
		  printf(" (%02d%%)",(int)( 100.*( (double)wrote/(double)read)));
		src.len=8*len;	//1octet = 8bits

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		LZ78_encode(&dst,&src);

		//printf("dst.len=%d\n",dst.len);
		fwrite(&dst.len,3, 1, out);
		fwrite(dst.data, ((dst.len)/8)+1,1,out);
		wrote += 3+(dst.len/8)+1;
	}
	//calcul de la taille du fichier de sortie
	fseek(out,0,SEEK_END);
	int fileLenOut = ftell(out);
	rewind(out);

	updateBar(1.);
	printf(" (%02d%%)",(int)( 100.*( (double)fileLenOut/(double)fileLen)));
	printf("\n :D\n");

	bit_freeBuf(&src);
	bit_freeBuf(&dst);
}

//-----------------------------------------------------------------------------
void LZ78_decompress(FILE * out, FILE * in)
//-----------------------------------------------------------------------------
{
	bitbuf_t src,dst;
	int bufLen=0;
	size_t wrote=0;
	lz78header header;

	LZ78_readHeader(in, &header);

	bufLen=header.bufLen;
	printf("bufLen =%dbytes oriSize=%dbytes\n",bufLen, header.oriSize);

	//initialisation des buffers
	bit_initBuf(&src,(bufLen+(bufLen/2))*8);
	bit_initBuf(&dst,bufLen*8);

	//initialisation de l'algo
	LZ78_init();

	updateBar(0.);

	while( ! feof(in) )
	{
		src.len=0;
		fread(&(src.len), 3,1,in);
		fread(src.data, 1, (src.len/8)+1, in);

		updateBar((double)wrote/header.oriSize);

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		LZ78_decode(&dst, &src);
		//printf("src.len=%d dst.len=%d\n",src.len,dst.len);
		fwrite(dst.data, dst.len/8, 1, out);	//dst.len = 8*k
		wrote+=dst.len/8;
	}
	updateBar((double)wrote/header.oriSize);
	printf("\n :D\n");

	bit_freeBuf(&src);
	bit_freeBuf(&dst);
}

/*
//-----------------------------------------------------------------------------
int main()
//-----------------------------------------------------------------------------
{
	bitbuf_t dst, src, dst2;
	uchar msg[]="aabbaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbaaabbaaaaabbaaabbabaaab\
aaaaaabbbbbbbbbbbaaabbaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbaabbaaaaaaaaaaaaaaaaa\
aaaaaaabbbbbbbbbbbaaabbaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbaaabbaaaaaaaaaaaaaaaa\
aaaaaaaabbbbbbbbbbbb";
	int len = 120;
	msg[len]='\0';
	//int i;

	printf("%s (%d)\n",msg,len);

	src.data = msg;
	src.len  = 8*len;
	src.curs = msg;
	src.bit  = 0x01;

	bit_initBuf(&dst, 8*len);
	bit_initBuf(&dst2, 8*len);

	//printf("dst.len = %d \n",(int)dst.len);

	bzero(dst.data, len);
	bzero(dst2.data, len);

	LZ78_init();

	LZ78_encode(&dst, &src);
	bit_print(&dst);
	//printf("lz78_encode => %dbits\n",(int)dst.len);

	bit_seek(&dst,0,0,BITSEEK_SET);
	//printf("seekset => %d\n",(int)bit_getpos(&dst));

	PTree_draw(&mem_tree[0],"APC.ps");
	LZ78_init();
	LZ78_decode(&dst2,&dst);
	printf("\n%s\n",dst2.data);
	PTree_draw(&mem_tree[0],"APC2.ps");

	return EXIT_SUCCESS;
}
*/


//
